import os
import math
from pygraph.classes.graph import graph
from pygraph.classes.digraph import digraph
from pygraph.algorithms.minmax import cut_tree
from pygraph.algorithms.accessibility import connected_components

def comp(x, y):
    if x.value < y.value:
        return -1
    if x.value == y.value:
        return 0
    return 1

class gomory_edge:
    def __init__(self):
        self.edge = ()
        self.value = 0.0

class vms:
    def __init__(self):
        self.quantity = 0
        self.vms = []
        self.matrix = {}
        self.graph = graph()
        self.ghtree = {}
    def load(self, vmf):
        loader = open(vmf, 'r')
        vlines = loader.readlines()
        for vline in vlines:
            tricell = vline.split()
            if len(tricell) == 1:
                self.quantity= int(tricell[0])
            if len(tricell) == 3:
                tri1 = int(tricell[0])
                tri2 = int(tricell[1])
                if not (tri1) in self.vms:
                    self.vms.append(tri1)
                    self.graph.add_node(tri1)
                if not (tri2) in self.vms:
                    self.vms.append(tri2)
                    self.graph.add_node(tri2)
                if not self.graph.has_edge((tri1, tri2)):
                    self.graph.add_edge((tri1, tri2), float(tricell[2]))
                else:
                    wt = self.graph.edge_weight((tri1, tri2)) + float(tricell[2])
                    self.graph.set_edge_weight((tri1, tri2), wt)
                if self.matrix.has_key(tri1):
                    self.matrix[tri1][tri2] = float(tricell[2])
                else:
                    self.matrix[tri1] = {}
                    self.matrix[tri1][tri2] = float(tricell[2])
                    
            else:
                continue
        self.ghtree = cut_tree(self.graph)
    def vm_mincut(self, vmlist, bsize):
        #print 'vm_mincut:',vmlist,bsize
        n = len(vmlist)
        #establish graph
        subgraph = graph()
        s = []
        for vmi in vmlist:
            subgraph.add_node(vmi)
        for vmi in vmlist:
            for vmj in vmlist:
                if self.graph.has_edge((vmi, vmj)) and not subgraph.has_edge((vmi, vmj)):
                    subgraph.add_edge((vmi, vmj), self.graph.edge_weight((vmi, vmj)))
        #get gomory-hu tree
        sub_ghtree = cut_tree(subgraph)
        gomory_list = []
        gomory_tree = graph()
        for key, value in sub_ghtree.items():
            if not gomory_tree.has_node(key[0]):
                gomory_tree.add_node(key[0])
            if not gomory_tree.has_node(key[1]):
                gomory_tree.add_node(key[1])
            gomory_tree.add_edge(key, value)
            gomory_element = gomory_edge()
            gomory_element.edge = key
            gomory_element.value = value
            gomory_list.append(gomory_element)
        gomory_list.sort(comp)
        k = len(bsize)
        backup_gomory_tree = graph()
        for nodei in gomory_tree.nodes():
            backup_gomory_tree.add_node(nodei)
        for edgei in gomory_tree.edges():
            if not backup_gomory_tree.has_edge(edgei):
                backup_gomory_tree.add_edge(edgei, gomory_tree.edge_weight(edgei))
        invalidn = {}
        for ni in gomory_tree.nodes():
            invalidn[ni] = False
        for i in range(k):
            si = set([])
            c1 = set([])
            c2 = set([])
            s.append(si)
            remains = len(gomory_tree.nodes())
            for ts, value in invalidn.items():
                if value == True:
                    remains = remains - 1
            if bsize[i] == remains and bsize[i] != 0:
                for ni in gomory_tree.nodes():
                    if not invalidn[ni]:
                        s[i].add(ni)
                #print 'remaining ', s[i]
            flag = False
            j = 0
            for j in range(len(gomory_list)):
                if gomory_tree.has_edge(gomory_list[j].edge):
                    gomory_tree.del_edge(gomory_list[j].edge)
                else:continue
                cpn = connected_components(gomory_tree)
                s1 = 0
                c = set([])
                for cnv in set(cpn.values()):
                    c = set([])
                    s1 = 0
                    for ni, nv in cpn.items():
                        if nv == cnv and invalidn[ni] != True:
                            s1 = s1 + 1
                            c.add(ni)
                    if s1 == bsize[i]:
                        c1 = c
                        flag = True
                        break
                if flag:
                    break
                else:
                    pass
            for edgei in backup_gomory_tree.edges():
                if gomory_tree.has_edge(edgei):
                    continue
                else:
                    gomory_tree.add_edge(edgei, backup_gomory_tree.edge_weight(edgei))
            for ni in c1:
                invalidn[ni] = True
            if len(c1) > 0:
                s[i] = c1
            
            n = n - bsize[i]
            #gomory_tree.add_edge(gomory_list[j].edge, gomory_list[j].value)
        for i in range(k):
            if len(s[i]) == 0:
                for inode in gomory_tree.nodes():
                    if invalidn[inode] == False:
                        s[i].add(inode)
                        invalidn[inode] = True
                        if len(s[i]) == bsize[i]:
                            break
        #print s
        return s
    def hasSum(self, tdic, target):
        n = len(set(tdic.values()))
        binary = 0
        pick = []
        sum = 0
        print tdic
        print n
        for binary in range(int(math.pow(2, n))):
            for i in range(n):
                if binary % math.pow(2, i + 1) / math.pow(2, i) >= 1:
                    pick.append(i)
            for index in pick:
                for key, value in tdic.items():
                    if value == index:
                        sum = sum + 1
            if target == sum:
                return pick
        return [] 
#fakevm = vms()
#fakevm.load('../vm.in')
#print fakevm.vm_mincut([14, 15], [0, 1, 1])